<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>哈希表-集合-映射-cnblog | 凌歆的博客</title>
    <meta name="generator" content="VuePress 1.9.5">
    <link rel="icon" href="/img/favicon.ico">
    <meta name="description" content="web前端技术博客,专注web前端学习与总结。JavaScript,js,ES6,TypeScript,vue,React,python,css3,html5,Node,git,github等技术文章。">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,markdown">
    <meta name="baidu-site-verification" content="7F55weZDDc">
    <meta name="theme-color" content="#11a8cd">
    
    <link rel="preload" href="/assets/css/0.styles.d9c8cf8c.css" as="style"><link rel="preload" href="/assets/js/app.57550e13.js" as="script"><link rel="preload" href="/assets/js/2.f014c35f.js" as="script"><link rel="preload" href="/assets/js/101.098ca5c8.js" as="script"><link rel="prefetch" href="/assets/js/10.03a98811.js"><link rel="prefetch" href="/assets/js/100.145e708e.js"><link rel="prefetch" href="/assets/js/102.4d45c69a.js"><link rel="prefetch" href="/assets/js/103.499de505.js"><link rel="prefetch" href="/assets/js/104.c2c1b9b6.js"><link rel="prefetch" href="/assets/js/105.4e9b0663.js"><link rel="prefetch" href="/assets/js/106.9bb8cf6f.js"><link rel="prefetch" href="/assets/js/107.a81b32d7.js"><link rel="prefetch" href="/assets/js/108.81511e67.js"><link rel="prefetch" href="/assets/js/109.6a6741bf.js"><link rel="prefetch" href="/assets/js/11.e8729182.js"><link rel="prefetch" href="/assets/js/110.de657fe7.js"><link rel="prefetch" href="/assets/js/111.b092af6d.js"><link rel="prefetch" href="/assets/js/112.2dca5709.js"><link rel="prefetch" href="/assets/js/113.dbed1fac.js"><link rel="prefetch" href="/assets/js/114.e95a0131.js"><link rel="prefetch" href="/assets/js/115.2e3e8285.js"><link rel="prefetch" href="/assets/js/116.e64f7fec.js"><link rel="prefetch" href="/assets/js/117.583552c9.js"><link rel="prefetch" href="/assets/js/118.aa5d18f0.js"><link rel="prefetch" href="/assets/js/119.0c7b52d7.js"><link rel="prefetch" href="/assets/js/12.d63acec2.js"><link rel="prefetch" href="/assets/js/120.13f86281.js"><link rel="prefetch" href="/assets/js/121.e2b5b7f9.js"><link rel="prefetch" href="/assets/js/122.5252216a.js"><link rel="prefetch" href="/assets/js/123.8b8a3503.js"><link rel="prefetch" href="/assets/js/124.60df855c.js"><link rel="prefetch" href="/assets/js/125.f073ab1c.js"><link rel="prefetch" href="/assets/js/126.7b73de6a.js"><link rel="prefetch" href="/assets/js/127.4e25971c.js"><link rel="prefetch" href="/assets/js/128.0edf0e06.js"><link rel="prefetch" href="/assets/js/129.5cb5a70a.js"><link rel="prefetch" href="/assets/js/13.2259ef71.js"><link rel="prefetch" href="/assets/js/130.00247fda.js"><link rel="prefetch" href="/assets/js/131.d6fc003a.js"><link rel="prefetch" href="/assets/js/132.1a32b18f.js"><link rel="prefetch" href="/assets/js/133.e46c0193.js"><link rel="prefetch" href="/assets/js/134.a6ad681f.js"><link rel="prefetch" href="/assets/js/135.2fcbe137.js"><link rel="prefetch" href="/assets/js/136.f69bf451.js"><link rel="prefetch" href="/assets/js/137.b9ef2fcc.js"><link rel="prefetch" href="/assets/js/138.7fdd9feb.js"><link rel="prefetch" href="/assets/js/139.a3a37c91.js"><link rel="prefetch" href="/assets/js/14.0d6b23b9.js"><link rel="prefetch" href="/assets/js/140.a7c013ae.js"><link rel="prefetch" href="/assets/js/141.956c36ce.js"><link rel="prefetch" href="/assets/js/142.5aacfe42.js"><link rel="prefetch" href="/assets/js/143.57d691ef.js"><link rel="prefetch" href="/assets/js/144.b1e5766e.js"><link rel="prefetch" href="/assets/js/145.463284b7.js"><link rel="prefetch" href="/assets/js/146.6cc6420c.js"><link rel="prefetch" href="/assets/js/147.5b78c5a2.js"><link rel="prefetch" href="/assets/js/148.8d1d7679.js"><link rel="prefetch" href="/assets/js/149.4e0eb213.js"><link rel="prefetch" href="/assets/js/15.f6fde69d.js"><link rel="prefetch" href="/assets/js/150.b183de37.js"><link rel="prefetch" href="/assets/js/151.729ae770.js"><link rel="prefetch" href="/assets/js/152.b1297018.js"><link rel="prefetch" href="/assets/js/153.bb991bca.js"><link rel="prefetch" href="/assets/js/154.6f2286aa.js"><link rel="prefetch" href="/assets/js/155.6a9c7e4d.js"><link rel="prefetch" href="/assets/js/156.f7bd535d.js"><link rel="prefetch" href="/assets/js/157.64c0065c.js"><link rel="prefetch" href="/assets/js/158.d31ae949.js"><link rel="prefetch" href="/assets/js/159.7daea8a7.js"><link rel="prefetch" href="/assets/js/16.7be21beb.js"><link rel="prefetch" href="/assets/js/160.33cc971a.js"><link rel="prefetch" href="/assets/js/161.1676442a.js"><link rel="prefetch" href="/assets/js/162.71378046.js"><link rel="prefetch" href="/assets/js/163.99e49959.js"><link rel="prefetch" href="/assets/js/164.306f07d2.js"><link rel="prefetch" href="/assets/js/165.170977c7.js"><link rel="prefetch" href="/assets/js/166.f8602525.js"><link rel="prefetch" href="/assets/js/167.eea5c001.js"><link rel="prefetch" href="/assets/js/168.0146a311.js"><link rel="prefetch" href="/assets/js/169.05f9c9d9.js"><link rel="prefetch" href="/assets/js/17.2543f471.js"><link rel="prefetch" href="/assets/js/170.25d602b2.js"><link rel="prefetch" href="/assets/js/171.1ada26a6.js"><link rel="prefetch" href="/assets/js/172.2a0f697c.js"><link rel="prefetch" href="/assets/js/173.230d8ca8.js"><link rel="prefetch" href="/assets/js/174.e3758a2b.js"><link rel="prefetch" href="/assets/js/175.0f19f8ea.js"><link rel="prefetch" href="/assets/js/176.bf70d37d.js"><link rel="prefetch" href="/assets/js/177.4400f272.js"><link rel="prefetch" href="/assets/js/178.85af7b89.js"><link rel="prefetch" href="/assets/js/179.4cfaaaa2.js"><link rel="prefetch" href="/assets/js/18.394415f8.js"><link rel="prefetch" href="/assets/js/180.449c8409.js"><link rel="prefetch" href="/assets/js/181.73276924.js"><link rel="prefetch" href="/assets/js/182.5fab25cc.js"><link rel="prefetch" href="/assets/js/183.ecd4934d.js"><link rel="prefetch" href="/assets/js/184.246092cf.js"><link rel="prefetch" href="/assets/js/185.c671cd86.js"><link rel="prefetch" href="/assets/js/186.49bd1963.js"><link rel="prefetch" href="/assets/js/187.1fb32764.js"><link rel="prefetch" href="/assets/js/188.7c6885e9.js"><link rel="prefetch" href="/assets/js/189.a8701dec.js"><link rel="prefetch" href="/assets/js/19.ca7db8ea.js"><link rel="prefetch" href="/assets/js/190.ae3d3bde.js"><link rel="prefetch" href="/assets/js/191.ad7cd44e.js"><link rel="prefetch" href="/assets/js/192.bc443842.js"><link rel="prefetch" href="/assets/js/193.e4755764.js"><link rel="prefetch" href="/assets/js/194.814112ce.js"><link rel="prefetch" href="/assets/js/195.1c0aaa80.js"><link rel="prefetch" href="/assets/js/196.a6bd7add.js"><link rel="prefetch" href="/assets/js/20.4e91cd31.js"><link rel="prefetch" href="/assets/js/21.f095e6e1.js"><link rel="prefetch" href="/assets/js/22.72f4b8ab.js"><link rel="prefetch" href="/assets/js/23.e94eb9d2.js"><link rel="prefetch" href="/assets/js/24.0eae7d6f.js"><link rel="prefetch" href="/assets/js/25.36157609.js"><link rel="prefetch" href="/assets/js/26.dc5b6cba.js"><link rel="prefetch" href="/assets/js/27.c19b7b63.js"><link rel="prefetch" href="/assets/js/28.3aceae59.js"><link rel="prefetch" href="/assets/js/29.536091b3.js"><link rel="prefetch" href="/assets/js/3.d11119c4.js"><link rel="prefetch" href="/assets/js/30.821a4a30.js"><link rel="prefetch" href="/assets/js/31.5238784c.js"><link rel="prefetch" href="/assets/js/32.10bc7179.js"><link rel="prefetch" href="/assets/js/33.c1ed69c9.js"><link rel="prefetch" href="/assets/js/34.8d384231.js"><link rel="prefetch" href="/assets/js/35.d8890e52.js"><link rel="prefetch" href="/assets/js/36.eca37ad5.js"><link rel="prefetch" href="/assets/js/37.802549e3.js"><link rel="prefetch" href="/assets/js/38.53841770.js"><link rel="prefetch" href="/assets/js/39.7ae44409.js"><link rel="prefetch" href="/assets/js/4.493b9bca.js"><link rel="prefetch" href="/assets/js/40.ce56364a.js"><link rel="prefetch" href="/assets/js/41.85f0114b.js"><link rel="prefetch" href="/assets/js/42.714da6e2.js"><link rel="prefetch" href="/assets/js/43.fee4437c.js"><link rel="prefetch" href="/assets/js/44.b039b68b.js"><link rel="prefetch" href="/assets/js/45.96a55605.js"><link rel="prefetch" href="/assets/js/46.956ffb03.js"><link rel="prefetch" href="/assets/js/47.147d9218.js"><link rel="prefetch" href="/assets/js/48.ff787b40.js"><link rel="prefetch" href="/assets/js/49.871eee87.js"><link rel="prefetch" href="/assets/js/5.e0ba07d7.js"><link rel="prefetch" href="/assets/js/50.99b7c29e.js"><link rel="prefetch" href="/assets/js/51.8ecbf4ba.js"><link rel="prefetch" href="/assets/js/52.53d91d7e.js"><link rel="prefetch" href="/assets/js/53.af8a0d2a.js"><link rel="prefetch" href="/assets/js/54.a2f848b5.js"><link rel="prefetch" href="/assets/js/55.267e9947.js"><link rel="prefetch" href="/assets/js/56.0b201c40.js"><link rel="prefetch" href="/assets/js/57.cbdfd6f7.js"><link rel="prefetch" href="/assets/js/58.636c0c3f.js"><link rel="prefetch" href="/assets/js/59.fc9216c4.js"><link rel="prefetch" href="/assets/js/6.b98373f2.js"><link rel="prefetch" href="/assets/js/60.34f16fc4.js"><link rel="prefetch" href="/assets/js/61.4d130bd8.js"><link rel="prefetch" href="/assets/js/62.927caa10.js"><link rel="prefetch" href="/assets/js/63.a451fee0.js"><link rel="prefetch" href="/assets/js/64.32a5d47b.js"><link rel="prefetch" href="/assets/js/65.bc099429.js"><link rel="prefetch" href="/assets/js/66.3953050d.js"><link rel="prefetch" href="/assets/js/67.e934823b.js"><link rel="prefetch" href="/assets/js/68.4bcb52b0.js"><link rel="prefetch" href="/assets/js/69.bede18c8.js"><link rel="prefetch" href="/assets/js/7.8de8df2d.js"><link rel="prefetch" href="/assets/js/70.fce1daac.js"><link rel="prefetch" href="/assets/js/71.ea0a8c5d.js"><link rel="prefetch" href="/assets/js/72.15382c9e.js"><link rel="prefetch" href="/assets/js/73.848364d3.js"><link rel="prefetch" href="/assets/js/74.5fd08a50.js"><link rel="prefetch" href="/assets/js/75.c937c70d.js"><link rel="prefetch" href="/assets/js/76.a0dacd5a.js"><link rel="prefetch" href="/assets/js/77.4019cc23.js"><link rel="prefetch" href="/assets/js/78.9676a9e1.js"><link rel="prefetch" href="/assets/js/79.e46e10d5.js"><link rel="prefetch" href="/assets/js/8.2098eb96.js"><link rel="prefetch" href="/assets/js/80.987e83cb.js"><link rel="prefetch" href="/assets/js/81.eb98ff36.js"><link rel="prefetch" href="/assets/js/82.623561a7.js"><link rel="prefetch" href="/assets/js/83.e256d909.js"><link rel="prefetch" href="/assets/js/84.7d06a550.js"><link rel="prefetch" href="/assets/js/85.b8d9879e.js"><link rel="prefetch" href="/assets/js/86.31c4581b.js"><link rel="prefetch" href="/assets/js/87.e06ee05e.js"><link rel="prefetch" href="/assets/js/88.81ef718d.js"><link rel="prefetch" href="/assets/js/89.ba237d2f.js"><link rel="prefetch" href="/assets/js/9.36092fd0.js"><link rel="prefetch" href="/assets/js/90.ad2c9d92.js"><link rel="prefetch" href="/assets/js/91.a661f52d.js"><link rel="prefetch" href="/assets/js/92.1c28035b.js"><link rel="prefetch" href="/assets/js/93.c8b8e3d6.js"><link rel="prefetch" href="/assets/js/94.b6bc4a44.js"><link rel="prefetch" href="/assets/js/95.92cea882.js"><link rel="prefetch" href="/assets/js/96.5373491b.js"><link rel="prefetch" href="/assets/js/97.bb39efc8.js"><link rel="prefetch" href="/assets/js/98.af7a030f.js"><link rel="prefetch" href="/assets/js/99.07dc87d8.js">
    <link rel="stylesheet" href="/assets/css/0.styles.d9c8cf8c.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png" alt="凌歆的博客" class="logo"> <span class="site-name can-hide">凌歆的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="https://lingxin-tanhua.oss-cn-shanghai.aliyuncs.com/QQ%E6%88%AA%E5%9B%BE20220503092755.png"> <div class="blogger-info"><h3>lingxin</h3> <span>凌歆</span></div></div> <nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="前端" class="dropdown-title"><a href="/web/" class="link-title">前端</a> <span class="title" style="display:none;">前端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>学习笔记</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/note/html/" class="nav-link">HTML笔记</a></li><li class="dropdown-subitem"><a href="/note/js-low/" class="nav-link">JavaScript基础笔记</a></li><li class="dropdown-subitem"><a href="/note/js-high/" class="nav-link">JavaScript高阶笔记</a></li><li class="dropdown-subitem"><a href="/note/js-dom-bom/" class="nav-link">JavaScript DOM和BOM笔记</a></li><li class="dropdown-subitem"><a href="/note/jquery/" class="nav-link">jQuery笔记</a></li><li class="dropdown-subitem"><a href="/note/ajax/" class="nav-link">Ajax笔记</a></li><li class="dropdown-subitem"><a href="/note/nodejs/" class="nav-link">NodeJs笔记</a></li><li class="dropdown-subitem"><a href="/note/reg/" class="nav-link">正则表达式笔记</a></li><li class="dropdown-subitem"><a href="/note/vue/" class="nav-link">Vue笔记</a></li><li class="dropdown-subitem"><a href="/note/react/" class="nav-link">react笔记</a></li><li class="dropdown-subitem"><a href="/note/wx/" class="nav-link">微信小程序笔记</a></li><li class="dropdown-subitem"><a href="/note/uniapp/" class="nav-link">uniapp笔记</a></li><li class="dropdown-subitem"><a href="/note/echarts/" class="nav-link">echarts笔记</a></li><li class="dropdown-subitem"><a href="/note/git/" class="nav-link">Git笔记</a></li></ul></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="后端" class="dropdown-title"><a href="/back/" class="link-title">后端</a> <span class="title" style="display:none;">后端</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/java/" class="nav-link">JAVA</a></li><li class="dropdown-item"><!----> <a href="/note/javaweb/" class="nav-link">JavaWeb</a></li><li class="dropdown-item"><!----> <a href="/note/mysql/" class="nav-link">MySql</a></li><li class="dropdown-item"><!----> <a href="/note/ssm/" class="nav-link">ssm</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法" class="dropdown-title"><a href="/algor/" class="link-title">算法</a> <span class="title" style="display:none;">算法</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/sf/" class="nav-link">算法训练营</a></li><li class="dropdown-item"><!----> <a href="/note/js-sf/" class="nav-link">js数据结构与算法</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="面试" class="dropdown-title"><a href="/mianshi/" class="link-title">面试</a> <span class="title" style="display:none;">面试</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/lqb/" class="nav-link">蓝桥杯备战</a></li><li class="dropdown-item"><!----> <a href="/note/ms/" class="nav-link">前端面试</a></li><li class="dropdown-item"><!----> <a href="/note/hmms/" class="nav-link">黑马面试</a></li><li class="dropdown-item"><!----> <a href="/note/xzms/" class="nav-link">校招零距离面试</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="解决方案" class="dropdown-title"><a href="/resolve/" class="link-title">解决方案</a> <span class="title" style="display:none;">解决方案</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/note/qd-resolve/" class="nav-link">前端解决方案</a></li><li class="dropdown-item"><!----> <a href="/note/hd-resolve/" class="nav-link">后端解决方案</a></li></ul></div></div><div class="nav-item"><a href="/pages/beb6c0bd8a66cea6/" class="nav-link">收藏</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="索引" class="dropdown-title"><a href="/archives/" class="link-title">索引</a> <span class="title" style="display:none;">索引</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">分类</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">标签</a></li><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">归档</a></li></ul></div></div> <a href="https://github.com/linxin1123/vuepress-blog" target="_blank" rel="noopener noreferrer" class="repo-link">
    GitHub
    <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>学习笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法训练营</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/8ebdeb/" class="sidebar-link">数组-链表-栈-队列-cnblog</a></li><li><a href="/pages/8585b9/" class="sidebar-link">数组-链表-栈-队列（下）-cnblog</a></li><li><a href="/pages/1848ee/" aria-current="page" class="active sidebar-link">哈希表-集合-映射-cnblog</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level2"><a href="/pages/1848ee/#哈希表-集合-映射" class="sidebar-link">哈希表-集合-映射</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header level4"><a href="/pages/1848ee/#_874-模拟行走机器人" class="sidebar-link">874. 模拟行走机器人</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#解题思路" class="sidebar-link">解题思路</a></li><li class="sidebar-sub-header level4"><a href="/pages/1848ee/#_49-字母异位词分组-模板题" class="sidebar-link">49. 字母异位词分组(模板题)</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#解题思路-2" class="sidebar-link">解题思路</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#完整代码" class="sidebar-link">完整代码</a></li><li class="sidebar-sub-header level4"><a href="/pages/1848ee/#_30-串联所有单词的子串" class="sidebar-link">30. 串联所有单词的子串</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#解题思路-3" class="sidebar-link">解题思路</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#完整代码-2" class="sidebar-link">完整代码</a></li><li class="sidebar-sub-header level4"><a href="/pages/1848ee/#_146-lru-缓存-高频题" class="sidebar-link">146. LRU 缓存(高频题)</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#解题思路-4" class="sidebar-link">解题思路</a></li><li class="sidebar-sub-header level5"><a href="/pages/1848ee/#完整代码-双向链表-hash" class="sidebar-link">完整代码（双向链表+hash）</a></li></ul></li></ul></li><li><a href="/pages/32c8c0/" class="sidebar-link">前缀和-差分-双指针（上）-cnblog</a></li><li><a href="/pages/9b8692/" class="sidebar-link">前缀和-差分-双指针（下）-cnblog</a></li><li><a href="/pages/7f3ede/" class="sidebar-link">算法训练营-排序-cnblog</a></li><li><a href="/pages/cbca68/" class="sidebar-link">二分</a></li><li><a href="/pages/1a456e/" class="sidebar-link">三分-二分答案</a></li><li><a href="/pages/3fd3d8/" class="sidebar-link">树与图-cnblog</a></li><li><a href="/pages/7c3255/" class="sidebar-link">二叉搜索树</a></li><li><a href="/pages/cf81aa/" class="sidebar-link">二叉堆</a></li><li><a href="/pages/1cde21/" class="sidebar-link">递归-分治</a></li><li><a href="/pages/0e21af/" class="sidebar-link">深度-广度搜索-状态空间-cnblog</a></li><li><a href="/pages/6789f3/" class="sidebar-link">动态规划(一)</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>js数据结构与算法</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"><div class="theme-vdoing-wrapper "><div class="articleInfo-wrap" data-v-06225672><div class="articleInfo" data-v-06225672><ul class="breadcrumbs" data-v-06225672><li data-v-06225672><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-06225672></a></li> <li data-v-06225672><a href="/algor/#算法" data-v-06225672>算法</a></li><li data-v-06225672><a href="/algor/#算法训练营" data-v-06225672>算法训练营</a></li></ul> <div class="info" data-v-06225672><div title="作者" class="author iconfont icon-touxiang" data-v-06225672><a href="https://github.com/linxin1123" target="_blank" title="作者" class="beLink" data-v-06225672>lingxin</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-06225672><a href="javascript:;" data-v-06225672>2023-02-17</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-title">目录</div> <div class="right-menu-content"></div></div></div> <h1><img src="">哈希表-集合-映射-cnblog<!----></h1>  <div class="theme-vdoing-content content__default"><h2 id="哈希表-集合-映射"><a href="#哈希表-集合-映射" class="header-anchor">#</a> 哈希表-集合-映射</h2> <h4 id="_874-模拟行走机器人"><a href="#_874-模拟行走机器人" class="header-anchor">#</a> 874. <a href="https://leetcode.cn/problems/walking-robot-simulation/" target="_blank" rel="noopener noreferrer">模拟行走机器人<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>机器人在一个无限大小的 XY 网格平面上行走，从点 <code>(0, 0)</code> 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 <code>commands</code> ：</p> <ul><li><code>-2</code> ：向左转 <code>90</code> 度</li> <li><code>-1</code> ：向右转 <code>90</code> 度</li> <li><code>1 &lt;= x &lt;= 9</code> ：向前移动 <code>x</code> 个单位长度</li></ul> <p>在网格上有一些格子被视为障碍物 <code>obstacles</code> 。第 <code>i</code> 个障碍物位于网格点  <code>obstacles[i] = (xi, yi)</code> 。</p> <p>机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，但仍然可以继续尝试进行该路线的其余部分。</p> <p>返回从原点到机器人所有经过的路径点（坐标为整数）的最大欧式距离的平方。（即，如果距离为 <code>5</code> ，则返回 <code>25</code> ）</p> <p><strong>注意：</strong></p> <ul><li>北表示 <code>+Y</code> 方向。</li> <li>东表示 <code>+X</code> 方向。</li> <li>南表示 <code>-Y</code> 方向。</li> <li>西表示 <code>-X</code> 方向。</li></ul> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：commands = [4,-1,4,-2,4], obstacles = [[2,4]]
输出：65
解释：机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)
4. 左转
5. 向北走 4 个单位，到达 (1, 8)
距离原点最远的是 (1, 8) ，距离为 12 + 82 = 65
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= commands.length &lt;= 104</code></li> <li><code>commands[i]</code> is one of the values in the list <code>[-2,-1,1,2,3,4,5,6,7,8,9]</code>.</li> <li><code>0 &lt;= obstacles.length &lt;= 104</code></li> <li><code>-3 * 104 &lt;= xi, yi &lt;= 3 * 104</code></li> <li>答案保证小于 <code>231</code></li></ul> <h5 id="解题思路"><a href="#解题思路" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 把障碍物位置存储到set中，hash实现，实现时间复杂度为O<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>,即输入一个值，hash函数处理，得到值（可以理解为下标），看是否能在set集合中找到下标是否存了值O<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>

<span class="token number">2</span>. 每走一步，确定下一步是否有障碍物，没有，继续行走，计算一个最大值
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br></div></div><div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">robotSim</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">commands<span class="token punctuation">,</span> obstacles</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token comment">// 使用set集合存放障碍物</span>
    <span class="token keyword">let</span> set<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Set</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>obstacles<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>obstacles<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token string">&quot;,&quot;</span><span class="token operator">+</span>obstacles<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 定义一个方向数组，即机器人往某个方向移动时，x，y的变化</span>

    <span class="token comment">// 0 N 1 E 2 S 3 W</span>

    <span class="token keyword">let</span> dx<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> dy<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span>

    <span class="token comment">// 初始方向北</span>
    <span class="token keyword">let</span> dir<span class="token operator">=</span><span class="token number">0</span>

    <span class="token comment">// 开始运行指令</span>
    <span class="token keyword">let</span> x<span class="token operator">=</span><span class="token number">0</span>
    <span class="token keyword">let</span> y<span class="token operator">=</span><span class="token number">0</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token number">0</span>

    commands<span class="token punctuation">.</span><span class="token function">forEach</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">command</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token comment">// console.log(command,index)</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>command<span class="token operator">===</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// 右转</span>
            dir<span class="token operator">=</span><span class="token punctuation">(</span>dir<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token operator">%</span><span class="token number">4</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span>command<span class="token operator">===</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// 左转</span>
            dir<span class="token operator">=</span><span class="token punctuation">(</span>dir<span class="token operator">+</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token operator">%</span><span class="token number">4</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            <span class="token comment">// 正常行走</span>
            <span class="token comment">// console.log(dir)</span>
            <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>j<span class="token operator">&lt;</span>command<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">let</span> nextX<span class="token operator">=</span>x<span class="token operator">+</span>dx<span class="token punctuation">[</span>dir<span class="token punctuation">]</span>
                <span class="token keyword">let</span> nextY<span class="token operator">=</span>y<span class="token operator">+</span>dy<span class="token punctuation">[</span>dir<span class="token punctuation">]</span>

                <span class="token comment">// 判断下一步的地方是否存在障碍物</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">has</span><span class="token punctuation">(</span>nextX<span class="token operator">+</span><span class="token string">&quot;,&quot;</span><span class="token operator">+</span>nextY<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
                    <span class="token comment">// console.log(1)</span>
                    <span class="token keyword">break</span>
                <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
                    x<span class="token operator">=</span>nextX
                    y<span class="token operator">=</span>nextY

                    res<span class="token operator">=</span>Math<span class="token punctuation">.</span><span class="token function">max</span><span class="token punctuation">(</span>res<span class="token punctuation">,</span>x<span class="token operator">*</span>x<span class="token operator">+</span>y<span class="token operator">*</span>y<span class="token punctuation">)</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span><span class="token punctuation">)</span>
        
    

    <span class="token comment">// console.log(x,y)</span>

    <span class="token keyword">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br></div></div><ul><li><p>注意点</p> <ul><li>方向数组（这个可以记忆，作为一个解决方案，因为判断每次行走的下一步位置比较复杂（使用if，eles））</li></ul> <div class="language-js line-numbers-mode"><pre class="language-js"><code> <span class="token comment">// 定义一个方向数组，即机器人往某个方向移动时，x，y的变化</span>

    <span class="token comment">// 0 N 1 E 2 S 3 W</span>

    <span class="token keyword">let</span> dx<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span>
    <span class="token keyword">let</span> dy<span class="token operator">=</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">]</span>

    <span class="token comment">// 初始方向北</span>
    <span class="token keyword">let</span> dir<span class="token operator">=</span><span class="token number">0</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div></li></ul> <h4 id="_49-字母异位词分组-模板题"><a href="#_49-字母异位词分组-模板题" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/group-anagrams/" target="_blank" rel="noopener noreferrer">49. 字母异位词分组(模板题)<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给你一个字符串数组，请你将 <strong>字母异位词</strong> 组合在一起。可以按任意顺序返回结果列表。</p> <p><strong>字母异位词</strong> 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。</p> <p><strong>示例 1:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: strs = [&quot;eat&quot;, &quot;tea&quot;, &quot;tan&quot;, &quot;ate&quot;, &quot;nat&quot;, &quot;bat&quot;]
输出: [[&quot;bat&quot;],[&quot;nat&quot;,&quot;tan&quot;],[&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 2:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: strs = [&quot;&quot;]
输出: [[&quot;&quot;]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>示例 3:</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入: strs = [&quot;a&quot;]
输出: [[&quot;a&quot;]]
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= strs.length &lt;= 104</code></li> <li><code>0 &lt;= strs[i].length &lt;= 100</code></li> <li><code>strs[i]</code> 仅包含小写字母</li></ul> <h5 id="解题思路-2"><a href="#解题思路-2" class="header-anchor">#</a> 解题思路</h5> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 一个单词字母出现次数相同，排列不同，我们把它分为一组

<span class="token number">3</span>. 那我们把单词的字母顺序都排好，创建排好序的str<span class="token operator">==</span><span class="token operator">&gt;</span><span class="token punctuation">[</span><span class="token punctuation">]</span>的映射
<span class="token number">4</span>. 遇到一个排好序的与str（key）相同，把排序前的字符串push到映射数组中
<span class="token number">5</span>. 最后我们把拍好序的映射数组输出
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><h5 id="完整代码"><a href="#完整代码" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string[]} strs
 * @return {string[][]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">groupAnagrams</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">strs</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 字母相同，排列不同，我们让它们的排列相同</span>

    <span class="token comment">// 我们设置排序字符串 和 其字符串数组的映射（如果排序后字符串与key相同，则push）</span>

    <span class="token keyword">let</span> m<span class="token operator">=</span><span class="token keyword">new</span> <span class="token class-name">Map</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> str <span class="token keyword">of</span> strs<span class="token punctuation">)</span><span class="token punctuation">{</span>
        
        <span class="token keyword">let</span> sortStr<span class="token operator">=</span>str<span class="token punctuation">.</span><span class="token function">split</span><span class="token punctuation">(</span><span class="token string">&quot;&quot;</span><span class="token punctuation">)</span>
        sortStr<span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">a<span class="token punctuation">,</span>b</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
           <span class="token keyword">return</span> a<span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span>b<span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token punctuation">)</span>

        sortStr<span class="token operator">=</span>sortStr<span class="token punctuation">.</span><span class="token function">join</span><span class="token punctuation">(</span><span class="token string">&quot;&quot;</span><span class="token punctuation">)</span>

        <span class="token comment">// 设置映射关系</span>
        <span class="token comment">// let res=m.has(sortStr) ? m.get(sortStr).push(str) : [].push(str)</span>
        
        <span class="token keyword">if</span><span class="token punctuation">(</span>m<span class="token punctuation">.</span><span class="token function">has</span><span class="token punctuation">(</span>sortStr<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// console.log(m.get(sortStr))</span>
            <span class="token keyword">let</span> arr<span class="token operator">=</span>m<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>sortStr<span class="token punctuation">)</span>
            arr<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span>
            
            m<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>sortStr<span class="token punctuation">,</span>arr<span class="token punctuation">)</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
            <span class="token keyword">let</span> arr<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
            arr<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span>
            m<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>sortStr<span class="token punctuation">,</span>arr<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">let</span> keys<span class="token operator">=</span>m<span class="token punctuation">.</span><span class="token function">keys</span><span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> key <span class="token keyword">of</span> keys<span class="token punctuation">)</span><span class="token punctuation">{</span>
        res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>m<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">return</span> res
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br></div></div><h4 id="_30-串联所有单词的子串"><a href="#_30-串联所有单词的子串" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/substring-with-concatenation-of-all-words/" target="_blank" rel="noopener noreferrer">30. 串联所有单词的子串<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>给定一个字符串 <code>s</code> 和一个字符串数组 <code>words</code><strong>。</strong> <code>words</code> 中所有字符串 <strong>长度相同</strong>。</p> <p><code>s</code> 中的 <strong>串联子串</strong> 是指一个包含 <code>words</code> 中所有字符串以任意顺序排列连接起来的子串。</p> <ul><li>例如，如果 <code>words = [&quot;ab&quot;,&quot;cd&quot;,&quot;ef&quot;]</code>， 那么 <code>&quot;abcdef&quot;</code>， <code>&quot;abefcd&quot;</code>，<code>&quot;cdabef&quot;</code>， <code>&quot;cdefab&quot;</code>，<code>&quot;efabcd&quot;</code>， 和 <code>&quot;efcdab&quot;</code> 都是串联子串。 <code>&quot;acdbef&quot;</code> 不是串联子串，因为他不是任何 <code>words</code> 排列的连接。</li></ul> <p>返回所有串联字串在 <code>s</code> 中的开始索引。你可以以 <strong>任意顺序</strong> 返回答案。</p> <p><strong>示例 1：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot;barfoothefoobarman&quot;, words = [&quot;foo&quot;,&quot;bar&quot;]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 &quot;barfoo&quot; 开始位置是 0。它是 words 中以 [&quot;bar&quot;,&quot;foo&quot;] 顺序排列的连接。
子串 &quot;foobar&quot; 开始位置是 9。它是 words 中以 [&quot;foo&quot;,&quot;bar&quot;] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p><strong>示例 2：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot;wordgoodgoodgoodbestword&quot;, words = [&quot;word&quot;,&quot;good&quot;,&quot;best&quot;,&quot;word&quot;]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br></div></div><p><strong>示例 3：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入：s = &quot;barfoofoobarthefoobarman&quot;, words = [&quot;bar&quot;,&quot;foo&quot;,&quot;the&quot;]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 &quot;foobarthe&quot; 开始位置是 6。它是 words 中以 [&quot;foo&quot;,&quot;bar&quot;,&quot;the&quot;] 顺序排列的连接。
子串 &quot;barthefoo&quot; 开始位置是 9。它是 words 中以 [&quot;bar&quot;,&quot;the&quot;,&quot;foo&quot;] 顺序排列的连接。
子串 &quot;thefoobar&quot; 开始位置是 12。它是 words 中以 [&quot;the&quot;,&quot;foo&quot;,&quot;bar&quot;] 顺序排列的连接。
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= s.length &lt;= 104</code></li> <li><code>1 &lt;= words.length &lt;= 5000</code></li> <li><code>1 &lt;= words[i].length &lt;= 30</code></li> <li><code>words[i]</code> 和 <code>s</code> 由小写英文字母组成</li></ul> <h5 id="解题思路-3"><a href="#解题思路-3" class="header-anchor">#</a> 解题思路</h5> <ul><li><p>==这题和49（上题思路一致）==</p></li> <li><p>这题我们把==单词作为字母==</p></li> <li><p>计算==单词出现的次数和给定的words数组中字母的出现次数是否相同==</p></li></ul> <h5 id="完整代码-2"><a href="#完整代码-2" class="header-anchor">#</a> 完整代码</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">findSubstring</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">s<span class="token punctuation">,</span> words</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>

    <span class="token keyword">let</span> res<span class="token operator">=</span><span class="token punctuation">[</span><span class="token punctuation">]</span>
    <span class="token comment">// words数组每个单词出现次数对象</span>
    <span class="token keyword">let</span> wordsObj<span class="token operator">=</span><span class="token punctuation">{</span><span class="token punctuation">}</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>words<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        wordsObj<span class="token punctuation">[</span>words<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">=</span>wordsObj<span class="token punctuation">[</span>words<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">===</span><span class="token keyword">undefined</span><span class="token operator">?</span> <span class="token number">1</span><span class="token operator">:</span>wordsObj<span class="token punctuation">[</span>words<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span>   
    <span class="token punctuation">}</span>
    <span class="token comment">// words数组每个单词出现次数对象</span>


    <span class="token comment">// 比较两个对象是否相同</span>
    <span class="token keyword">const</span> <span class="token function-variable function">compareObj</span><span class="token operator">=</span><span class="token punctuation">(</span><span class="token parameter">obj1<span class="token punctuation">,</span>obj2</span><span class="token punctuation">)</span><span class="token operator">=&gt;</span><span class="token punctuation">{</span>
        <span class="token keyword">let</span> obj1Props<span class="token operator">=</span>Object<span class="token punctuation">.</span><span class="token function">getOwnPropertyNames</span><span class="token punctuation">(</span>obj1<span class="token punctuation">)</span>
        <span class="token keyword">let</span> obj2Props<span class="token operator">=</span>Object<span class="token punctuation">.</span><span class="token function">getOwnPropertyNames</span><span class="token punctuation">(</span>obj2<span class="token punctuation">)</span>

        <span class="token comment">// 属性长度是否相同</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span>obj1Props<span class="token punctuation">.</span>length<span class="token operator">!==</span>obj2Props<span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token boolean">false</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;</span>obj1Props<span class="token punctuation">.</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            propName<span class="token operator">=</span>obj1Props<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
            <span class="token keyword">let</span> a<span class="token operator">=</span>obj1<span class="token punctuation">[</span>propName<span class="token punctuation">]</span>
            <span class="token keyword">let</span> b<span class="token operator">=</span>obj2<span class="token punctuation">[</span>propName<span class="token punctuation">]</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span>a<span class="token operator">!==</span>b<span class="token punctuation">)</span><span class="token punctuation">{</span>
                <span class="token keyword">return</span> <span class="token boolean">false</span>
            <span class="token punctuation">}</span>  
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> <span class="token boolean">true</span>
    <span class="token punctuation">}</span>


    <span class="token comment">// 枚举可能的字串</span>
    <span class="token comment">// 字串长度</span>
    <span class="token keyword">let</span> length<span class="token operator">=</span>words<span class="token punctuation">.</span>length<span class="token operator">*</span>words<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length

    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>i<span class="token operator">&lt;=</span>s<span class="token punctuation">.</span>length<span class="token operator">-</span>length<span class="token punctuation">;</span>i<span class="token operator">++</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        
        <span class="token keyword">let</span> sObj<span class="token operator">=</span><span class="token punctuation">{</span><span class="token punctuation">}</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">let</span> j<span class="token operator">=</span>i<span class="token punctuation">;</span>j<span class="token operator">&lt;</span>i<span class="token operator">+</span>length<span class="token punctuation">;</span>j<span class="token operator">+=</span>words<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span><span class="token punctuation">{</span>
            <span class="token comment">// 判断i到i+length这个字串是否包含words数组 </span>
            <span class="token comment">// 把字符串切成words.length份</span>
            <span class="token comment">// let subStr=s.slice(i+j*words.length,i+((j+1)*words.length))</span>

            <span class="token keyword">let</span> subStr<span class="token operator">=</span>s<span class="token punctuation">.</span><span class="token function">slice</span><span class="token punctuation">(</span>j<span class="token punctuation">,</span>j<span class="token operator">+</span>words<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>length<span class="token punctuation">)</span>

            sObj<span class="token punctuation">[</span>subStr<span class="token punctuation">]</span><span class="token operator">=</span>sObj<span class="token punctuation">[</span>subStr<span class="token punctuation">]</span><span class="token operator">===</span><span class="token keyword">undefined</span><span class="token operator">?</span> <span class="token number">1</span><span class="token operator">:</span>sObj<span class="token punctuation">[</span>subStr<span class="token punctuation">]</span><span class="token operator">+</span><span class="token number">1</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 判断一下sObj 与wordsObj是否相同</span>

        <span class="token comment">// console.log(sObj,wordsObj)</span>

        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token function">compareObj</span><span class="token punctuation">(</span>wordsObj<span class="token punctuation">,</span>sObj<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
            res<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>



    <span class="token keyword">return</span> res

<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br></div></div><h4 id="_146-lru-缓存-高频题"><a href="#_146-lru-缓存-高频题" class="header-anchor">#</a> <a href="https://leetcode.cn/problems/lru-cache/description/" target="_blank" rel="noopener noreferrer">146. LRU 缓存(高频题)<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></h4> <p>请你设计并实现一个满足 <a href="https://baike.baidu.com/item/LRU" target="_blank" rel="noopener noreferrer">LRU (最近最少使用) 缓存<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> 约束的数据结构。</p> <p>实现 <code>LRUCache</code> 类：</p> <ul><li><code>LRUCache(int capacity)</code> 以 <strong>正整数</strong> 作为容量 <code>capacity</code> 初始化 LRU 缓存</li> <li><code>int get(int key)</code> 如果关键字 <code>key</code> 存在于缓存中，则返回关键字的值，否则返回 <code>-1</code> 。</li> <li><code>void put(int key, int value)</code> 如果关键字 <code>key</code> 已经存在，则变更其数据值 <code>value</code> ；如果不存在，则向缓存中插入该组 <code>key-value</code> 。如果插入操作导致关键字数量超过 <code>capacity</code> ，则应该 <strong>逐出</strong> 最久未使用的关键字。</li></ul> <p>函数 <code>get</code> 和 <code>put</code> 必须以 <code>O(1)</code> 的平均时间复杂度运行。</p> <p><strong>示例：</strong></p> <div class="language- line-numbers-mode"><pre class="language-text"><code>输入
[&quot;LRUCache&quot;, &quot;put&quot;, &quot;put&quot;, &quot;get&quot;, &quot;put&quot;, &quot;get&quot;, &quot;put&quot;, &quot;get&quot;, &quot;get&quot;, &quot;get&quot;]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br></div></div><p><strong>提示：</strong></p> <ul><li><code>1 &lt;= capacity &lt;= 3000</code></li> <li><code>0 &lt;= key &lt;= 10000</code></li> <li><code>0 &lt;= value &lt;= 105</code></li> <li>最多调用 <code>2 * 105</code> 次 <code>get</code> 和 <code>put</code></li></ul> <h5 id="解题思路-4"><a href="#解题思路-4" class="header-anchor">#</a> 解题思路</h5> <p><img src="https://img2023.cnblogs.com/blog/3089561/202302/3089561-20230203130540203-1508754611.png" alt=""></p> <div class="language-shell line-numbers-mode"><pre class="language-shell"><code><span class="token number">1</span>. 最近最少使用，当容量达到最大时，每次挤出的都停留时间最长的<span class="token operator">==</span><span class="token operator">=</span><span class="token operator">&gt;</span>可以使用最大堆（优先队列）

<span class="token number">2</span>. 使用双向链表+hash表，双向链表在删除和插入时为O<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span>,而在查询是为O<span class="token punctuation">(</span>n<span class="token punctuation">)</span> ，我们可以维护一个地址hash表（key<span class="token operator">==</span><span class="token operator">&gt;</span>node） node为链表节点地址
    每次进入一个元素时（超出容量），看是否在hash表中，如果存在，则把hash表对应的节点删除，在重新在头部插入
    不存在则删除最后一个节点，把新节点存入链表头部
    同时保存hash映射 <span class="token assign-left variable">key</span><span class="token operator">==</span><span class="token operator">&gt;</span>node


</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br></div></div><h5 id="完整代码-双向链表-hash"><a href="#完整代码-双向链表-hash" class="header-anchor">#</a> 完整代码（双向链表+hash）</h5> <div class="language-js line-numbers-mode"><pre class="language-js"><code><span class="token comment">// 解题思路</span>
<span class="token comment">// 最近最少使用</span>
<span class="token comment">// get和put都会算作访问最新的</span>

<span class="token comment">// 1. 使用优先队列（最大堆），每次返回停留时间最长的</span>
<span class="token comment">// 2. 使用双向链表+hash表（存放存入cache的地址），方便查询操作为O(1)</span>

<span class="token comment">// node的数据结构</span>
<span class="token keyword">var</span> <span class="token function-variable function">Node</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">key<span class="token punctuation">,</span> value<span class="token punctuation">,</span> pre<span class="token punctuation">,</span> next</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>key <span class="token operator">=</span> key <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">undefined</span> <span class="token operator">:</span> key
  <span class="token keyword">this</span><span class="token punctuation">.</span>value <span class="token operator">=</span> value <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">undefined</span> <span class="token operator">:</span> value
  <span class="token keyword">this</span><span class="token punctuation">.</span>pre <span class="token operator">=</span> pre <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">undefined</span> <span class="token operator">:</span> pre
  <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next <span class="token operator">===</span> <span class="token keyword">undefined</span> <span class="token operator">?</span> <span class="token keyword">undefined</span> <span class="token operator">:</span> next
<span class="token punctuation">}</span>

<span class="token comment">/**
 * @param {number} capacity
 */</span>

<span class="token comment">// 全局变量，存储一下cache最大值</span>
<span class="token comment">// var capacity = 0</span>
<span class="token keyword">var</span> <span class="token function-variable function">LRUCache</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">capacity</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>maxCapacity <span class="token operator">=</span> capacity
  <span class="token comment">// 链表，我们创建保护节点</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>capacity <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>map <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Map</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectTail <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>protectTail
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectTail<span class="token punctuation">.</span>pre <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead
<span class="token punctuation">}</span>

<span class="token comment">/**
 * @param {number} key
 * @return {number}
 */</span>
<span class="token class-name">LRUCache</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">get</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">key</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 刷新访问</span>
    <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">removeNode</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insertNode</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> node<span class="token punctuation">.</span>value<span class="token punctuation">)</span>
    <span class="token keyword">return</span> node<span class="token punctuation">.</span>value
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
    <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */</span>
<span class="token class-name">LRUCache</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">put</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">key<span class="token punctuation">,</span> value</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token comment">//这里使用头插法，最新的protectHead指向</span>

  <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">has</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 删除该节点，再重新插入</span>
    <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">removeNode</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>key<span class="token punctuation">)</span><span class="token punctuation">)</span>
    <span class="token comment">// node.value=value</span>
    <span class="token keyword">delete</span> node
    <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insertNode</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> value<span class="token punctuation">)</span>
  <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>capacity <span class="token operator">+</span> <span class="token number">1</span> <span class="token operator">&gt;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>maxCapacity<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token comment">// 超出cache最大值</span>
      <span class="token comment">// 把链表的尾部节点去除</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">removeNode</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>protectTail<span class="token punctuation">.</span>pre<span class="token punctuation">)</span>

      <span class="token comment">// 新的插入</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insertNode</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> value<span class="token punctuation">)</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
      <span class="token keyword">this</span><span class="token punctuation">.</span>capacity<span class="token operator">++</span>

      <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insertNode</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> value<span class="token punctuation">)</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token class-name">LRUCache</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">insertNode</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">key<span class="token punctuation">,</span> value</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Node</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> value<span class="token punctuation">)</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">set</span><span class="token punctuation">(</span>key<span class="token punctuation">,</span> node<span class="token punctuation">)</span>

  <span class="token comment">// 头插入链表</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead<span class="token punctuation">.</span>next<span class="token punctuation">.</span>pre <span class="token operator">=</span> node
  node<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead<span class="token punctuation">.</span>next
  <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead<span class="token punctuation">.</span>next <span class="token operator">=</span> node
  node<span class="token punctuation">.</span>pre <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>protectHead
<span class="token punctuation">}</span>

<span class="token class-name">LRUCache</span><span class="token punctuation">.</span>prototype<span class="token punctuation">.</span><span class="token function-variable function">removeNode</span> <span class="token operator">=</span> <span class="token keyword">function</span> <span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">this</span><span class="token punctuation">.</span>map<span class="token punctuation">.</span><span class="token function">delete</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>key<span class="token punctuation">)</span>
  node<span class="token punctuation">.</span>pre<span class="token punctuation">.</span>next <span class="token operator">=</span> node<span class="token punctuation">.</span>next
  node<span class="token punctuation">.</span>next<span class="token punctuation">.</span>pre <span class="token operator">=</span> node<span class="token punctuation">.</span>pre

  <span class="token keyword">return</span> node
<span class="token punctuation">}</span>

</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br><span class="line-number">81</span><br><span class="line-number">82</span><br><span class="line-number">83</span><br><span class="line-number">84</span><br><span class="line-number">85</span><br><span class="line-number">86</span><br><span class="line-number">87</span><br><span class="line-number">88</span><br><span class="line-number">89</span><br><span class="line-number">90</span><br><span class="line-number">91</span><br><span class="line-number">92</span><br><span class="line-number">93</span><br><span class="line-number">94</span><br><span class="line-number">95</span><br></div></div></div></div>  <div class="page-edit"><div class="edit-link"><a href="https://github.com/linxin1123/vuepress-blog/edit/master/docs/07.算法/41.算法训练营/03.哈希表-集合-映射-cnblog.md" target="_blank" rel="noopener noreferrer">编辑</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">2023/02/17, 11:29:32</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/8585b9/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">数组-链表-栈-队列（下）-cnblog</div></a> <a href="/pages/32c8c0/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">前缀和-差分-双指针（上）-cnblog</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/8585b9/" class="prev">数组-链表-栈-队列（下）-cnblog</a></span> <span class="next"><a href="/pages/32c8c0/">前缀和-差分-双指针（上）-cnblog</a>→
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/0b785d/"><div>
            Vuex
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/c59cc0/"><div>
            Vue响应式原理
            <!----></div></a> <span class="date">03-14</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/83cc7a/"><div>
            Vue虚拟DOM-cnblog
            <!----></div></a> <span class="date">03-14</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div></main></div> <div class="footer"><div class="icons"><a href="3010733382@qq.com" title="发邮件" target="_blank" class="iconfont icon-youjian"></a><a href="https://github.com/linxin1123" title="GitHub" target="_blank" class="iconfont icon-github"></a><a href="https://music.163.com/#/playlist?id=755597173" title="听音乐" target="_blank" class="iconfont icon-erji"></a></div> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2022-2023
    <span>lingxin | <a href="https://github.com/linxin1123/vuepress-blog/blob/master/LICENSE" target="_blank">MIT License</a></span></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div> <div title="主题模式" class="button blur theme-mode-but iconfont icon-zhuti"><ul class="select-box" style="display:none;"><li class="iconfont icon-zidong">
          跟随系统
        </li><li class="iconfont icon-rijianmoshi">
          浅色模式
        </li><li class="iconfont icon-yejianmoshi">
          深色模式
        </li><li class="iconfont icon-yuedu">
          阅读模式
        </li></ul></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div></div></div>
    <script src="/assets/js/app.57550e13.js" defer></script><script src="/assets/js/2.f014c35f.js" defer></script><script src="/assets/js/101.098ca5c8.js" defer></script>
  </body>
</html>
